import numpy as np


class KM_Algorithm:
    """
        KM算法，用于求解最大二分图匹配问题，将Planner中的优势函数矩阵输入到Net权重矩阵，输出匹配结果
    """
    def __init__(self,Net,flag=0,Num = 0):

        self.Net = Net
        # self.flag = flag
        self.resultNum = len(self.Net)
        self.Number = len(self.Net)
       # print(self.Number,len(self.Net[0]),self.Net)
        self.ux = np.zeros(self.Number,dtype=int) #variable for record path
        self.uy =np.zeros(len(self.Net[0]),dtype=int)
        self.lx,self.ly = np.zeros(self.Number,dtype=float),np.zeros(len(self.Net[0]),dtype=float)  #sign
        self.result = np.zeros(len(self.Net[0]),dtype=int)  #Store the final result
        self.inc = 99999
        # Net：权重矩阵，表示二分图的边的权重。
        # flag和Num：标志变量和数值变量，用于后续计算。
        # ux和uy：用于记录探索路径的数组。
        # lx和ly：顶点标记，用于维持对偶性。
        # result：存储匹配结果。
        # inc：用于记录当前的最小改进值。


    def match(self,u):

      #  global inc
        u = int(u)
        self.ux[u] = 1  #record node that was explored
       # print("Matching point:"+str(u))
        for v in range(len(self.Net[0])):
            #if(Net[u][v] == lx[u] + ly[v] and uy[v] == 0):
            if (self.uy[v] == 0):
                t = round(self.lx[u] + self.ly[v],2) - self.Net[u][v]
                if((abs(t)) < 0.1):   #it means here is possible to find a pair
                    #print(str(abs(t))+" is in!")
                    self.uy[v] = 1
                   # print('current result[i]:'+str(self.result[v]))
                    if(self.result[v] == -1 or self.match(self.result[v])):
                        # print("success! the match is :")
                        # print(u,v)
                        self.result[v] = u
                        return 1
                elif(self.inc > t):
                    self.inc = t
                   # print("current inc is :"+str(self.inc))
        return 0

    def Kuh_Munkras(self):
        #initialize lx,ly
        for  k in range(len(self.Net[0])):
            self.result[k] = -1
        for p in range(self.Number):

            self.ly[p] = 0.0
            self.result[p] = -1
            self.lx[p] = -999999.0 #minus infinite
            for q in range(len(self.Net[0])):
                if(self.lx[p] < self.Net[p][q]):    #Choose the biggest value to lx[i]
                    self.lx[p] = self.Net[p][q]

       # print(self.lx,self.ly)

        #find the perfect match
        for u in range(self.Number):
            while(1):
               # time.sleep(1)
                self.inc = 999999  # the minimum gap
                self.coverUsed()
                if(self.match(u)):
                    break

                for i in  range(self.Number):  #Change sign,and try again
                    if (self.ux[i]):
                        self.lx[i] -= self.inc
                    if (self.uy[i]):
                        self.ly[i] += self.inc
                   # print(self.lx[i],self.ly[i])


    # def calculateSum(self):
    #     sum = 0
    #     if(self.flag == 0):
    #         for i in range(len(self.Net[0])):
    #             if(self.result[i] >= self.resultNum ):
    #                 continue
    #             sum += self.Net[self.result[i]][i]
    #     elif(self.flag == 1):
    #         for i in range(0,self.resultNum ):
    #             sum += self.Net[self.result[i]][i]
    #     return sum

    def getResult(self):
        return self.result

    def set_Net(self,Net):
        self.Net = Net

    def coverUsed(self):
        self.ux, self.uy = np.zeros(self.Number, dtype=int), np.zeros(len(self.Net[0]),dtype=int)  # variable for record path
